Лемма Шепли — Фолкмана

Сложение четырёх множеств по Минковскому. Тёмно-красные точки обозначают элементы множеств, в то время как выпуклые оболочки множеств выделены розовым цветом. Точка (+) на правой иллюстрации, принадлежащая выпуклой оболочке суммы Минковского четырёх невыпуклых множеств, является суммой четырёх точек (+), представленных на левой иллюстрации.

Лемма Шепли — Фолкмана связывает две операции выпуклой геометрии — сложение по Минковскому и выпуклую оболочку. Лемма имеет приложения в ряде дисциплин, в том числе в математической экономике, оптимизации и теории вероятностей. Лемма и связанные с ней результаты позволяют дать утвердительный ответ на вопрос «Близка ли к состоянию выпуклости сумма нескольких множеств?».

Лемма названа в честь Ллойда Шепли и Джона Фолкмана и была впервые опубликована в работе экономиста Росса Старра. В 2012 году Шепли наравне с Элвином Ротом стал лауреатом Нобелевской премии по экономике. Работа Старра, в которой произошло первое упоминание леммы, увидела свет в 1969 году. Тогда экономист сотрудничал с известнейшим американским учёным Кеннетом Эрроу и занимался решением вопроса о существовании некоторых экономических равновесий. В работе Старра проводилось исследование экономики, в которой некоторые геометрически выраженные взаимосвязи, обладавшие свойством невыпуклости, заменялись ближайшими выпуклыми аналогами — выпуклыми оболочками. Старр доказал, что такая «овыпукленная» экономика обладает равновесными состояниями, весьма близкими к квазиравновесиям оригинальной экономики. Более того, учёный доказал, что каждое квазиравновесие обладает рядом оптимальных характеристик подлинного равновесия, которые были найдены в выпуклых экономиках. Работы Шепли, Фолкмана и Старра показали, что основные результаты выпуклой экономической теории являются хорошими приближениями экономики с невыпуклыми элементами. Лемма позволяет предположить, что если число слагаемых множеств превосходит размерность векторного пространства D, то тогда нахождение выпуклых оболочек («овыпукление») требуется только для D слагаемых. Французский экономист Роже Геснери писал: «Получение этих результатов в общем виде стало одним из главных достижений послевоенной экономической теории».

Тематика невыпуклых множеств в экономике становилась предметом исследования многих других нобелевских лауреатов. С этим вопросом работали Пол Самуэльсон (премия 1970 года), Кеннет Эрроу (1972), Тьяллинг Купманс (1975), Жерар Дебрё (1983), Роберт Ауман (2005), Пол Кругман (2008). Смежной тематикой выпуклых множеств занимались Леонид Канторович (1975), Роберт Солоу (1987), Леонид Гурвич (2007). В теории оптимизации лемма Шепли — Фолкмана использовалась для объяснения успешного решения задач минимизации сумм нескольких функций, а также для доказательства «закона средних» для случайных множеств (эта теорема была доказана только для выпуклых множеств).

Рассматриваемые категории

Лемма опирается на некоторые математические категории и результаты выпуклой геометрии.

Вещественное векторное пространство

Основная статья: Векторное пространство

Векторным пространством $V$ называется алгебраическая структура, для элементов которой определены две операции — сложение и умножение на число (называемое «скаляром»). При этом операции подчинены восьми аксиомам:

1. $\mathbf {x} +\mathbf {y} =\mathbf {y} +\mathbf {x}$, для любых $\mathbf {x} ,\mathbf {y} \in V$ (коммутативность сложения);
2. $\mathbf {x} +(\mathbf {y} +\mathbf {z} )=(\mathbf {x} +\mathbf {y} )+\mathbf {z}$, для любых $\mathbf {x} ,\mathbf {y} ,\mathbf {z} \in V$ (ассоциативность сложения);
3. существует такой элемент $\theta \in V$, что $\mathbf {x} +\theta =\mathbf {x}$ для любого $\mathbf {x} \in V$ (существование нейтрального элемента относительно сложения), в частности $V$ не пусто;
4. для любого $\mathbf {x} \in V$ существует такой элемент $-\mathbf {x} \in V$, что $\mathbf {x} +(-\mathbf {x} )=\theta$ (существование противоположного элемента относительно сложения).
5. $\lambda (\mu \mathbf {x} )=(\lambda \mu )\mathbf {x}$ (ассоциативность умножения на скаляр);
6. $1\cdot \mathbf {x} =\mathbf {x}$ (унитарность: умножение на нейтральный по умножению скаляр сохраняет вектор).
7. $(\lambda +\mu )\mathbf {x} =\lambda \mathbf {x} +\mu \mathbf {x}$ (дистрибутивность умножения на вектор относительно сложения скаляров);
8. $\lambda (\mathbf {x} +\mathbf {y} )=\lambda \mathbf {x} +\lambda \mathbf {y}$ (дистрибутивность умножения на скаляр относительно сложения векторов),

где $V$ — непустое множество элементов («векторов») данного пространства.

Важной характеристикой векторного пространства является размерность, которая характеризует максимальное число линейно независимых элементов пространства. Эти линейно независимые элементы образуют базис векторного пространства.

Выпуклое множество

Основная статья: Выпуклое множество

Если отрезок, соединяющий две любые точки множества Q, является его подмножеством, то Q выпукло.

Если отрезок, соединяющий две любые точки множества Q, не является его подмножеством, то Q невыпукло.

Отрезки позволяют определить, является ли подмножество выпуклым.

Непустое множество $Q$ в вещественном векторном пространстве считается выпуклым, если отрезок, соединяющий две любые точки $Q$, является подмножеством $Q$. Например, невыпуклое множество целых чисел {0, 1, 2} является подмножеством промежутка [0, 2], который обладает свойством выпуклости. Круг $\bullet$ является выпуклым множеством, а окружность $\circ$ таковым считаться не может, так как не все точки отрезка будут одновременно являться точками множества: $\oslash$. Пустое множество считается выпуклым либо по определению, либо на основании принципа пустой правды.

Формально выпуклое множество можно определить следующим образом:

Множество $Q$ является выпуклым, если для любых точек $v_{0}$, $v_{1}\in Q$ и любого вещественного числа $\lambda \in [0,1]$ выполняется условие

$(1-\lambda )v_{0}+\lambda v_{1}\in Q$.

Выпуклой комбинацией множества называется некоторая взвешенная средняя, определённая по формуле

$\sum _{i=1}^{n}\lambda _{i}v_{i}$

при условиях

${\begin{cases}\lambda _{i}\geqslant 0,\\\sum _{i=1}^{n}\lambda _{i}=1.\end{cases}}$

Используя метод математической индукции, можно установить, что множество $Q$ выпукло тогда и только тогда, когда каждая выпуклая комбинация $Q$ принадлежит самому множеству:

$\sum _{i=1}^{n}\lambda _{i}v_{i}\in Q$.

Определение выпуклого множества предполагает, что пересечение двух выпуклых множеств всегда выпукло. Отсюда же следует, что выпуклым является и пересечение семейства выпуклых множеств. В частности, пара непересекающихся множеств имеет пересечением пустое множество, которое, как было установлено выше, выпукло.

Выпуклая оболочка

Основная статья: Выпуклая оболочка

В выпуклой оболочке красного множества каждая синяя точка является выпуклой комбинацией некоторых красных точек.

Выпуклой оболочкой $ConvQ$ множества $Q$ называется наименьшее выпуклое множество, содержащее $Q$ в качестве подмножества. Наименьшее множество представляет собой наименьший элемент по отношению к вложению множеств, то есть такое выпуклое множество, содержащее данную фигуру, что оно содержится в любом другом выпуклом множестве, содержащем данную фигуру. Так, $ConvQ$ является пересечением всех выпуклых множеств, которые покрывают $Q$. К примеру, выпуклой оболочкой множества {0, 1} является отрезок числовой прямой [0, 1], содержащий целые числа 0 и 1.

Сложение Минковского

Основная статья: Сложение Минковского

Сложение множеств по Минковскому. Суммой квадратов Q₁=[0,1]² и Q₂=[1,2]² является квадрат Q₁+Q₂=[1,3]².

Суммой Минковского непустых множеств $Q_{1}$ и $Q_{2}$ в вещественном векторном пространстве является множество $Q_{3}$, состоящее из сумм всевозможных элементов слагаемых множеств:

$Q_{3}=\left\{\,q_{3}\mid q_{3}=q_{1}+q_{2},q_{1}\in Q_{1},q_{2}\in Q_{2}\,\right\}.$

Итак, в результате проведения операции формируется множество-сумма, включающее все возможные суммы элементов первого и второго множеств. Например, если множество, состоящее из нуля и единицы, сложить с собой же, то в результате будет получено множество, включающее ноль, единицу и двойку:

$\{0,1\}+\{0,1\}=\{0+0,0+1,1+0,1+1\}=\{0,1,2\}.$

Согласно методу математической индукции, сумма Минковского $Q_{n}$ конечного семейства непустых множеств при условиях

${\begin{cases}Q_{n}\neq \varnothing ,\\1\leqslant n\leqslant N.\\\end{cases}}$

является множеством, сформированным поэлементным сложением множеств-слагаемых:

$\sum Q_{n}=\{\sum q_{n}:q_{n}\in Q_{n}\}$.

Сумма множества $Q$ и множества $\{0\}$, содержащего только один нулевой элемент, равна $Q$:

$Q+\{0\}=Q$.

Выпуклая оболочка суммы Минковского

Операция сложения Минковского обладает полезным свойством при «овыпуклении» множеств, то есть при нахождении их выпуклых оболочек. Для любых множеств $Q_{1}$ и $Q_{2}$ в вещественном векторном пространстве выпуклая оболочка их суммы Минковского равна сумме Минковского их выпуклых оболочек:

$Conv(Q_{1}+Q_{2})=ConvQ_{1}+ConvQ_{2}$.

С применением математической индукции выводится аналогичное утверждение для конечного набора множеств:

$Conv(\sum Q_{n})=\sum Conv(Q_{n})$.

Лемма

Тождество

$Conv(\sum Q_{n})=\sum Conv(Q_{n})$

позволяет установить, что если точка $v$ принадлежит выпуклой оболочке суммы Минковского $N$ множеств, то она принадлежит и сумме выпуклых оболочек слагаемых множеств:

$v\in Conv(\sum Q_{n})\Rightarrow v\in \sum Conv(Q_{n})$

Из этой импликации и определения суммы Минковского следует, что любую точку, принадлежащую множеству $Conv(\sum Q_{n})$ можно представить как сумму некоторых точек $q_{n}$, принадлежащих выпуклым оболочкам слагаемых множеств:

${\begin{cases}v=\sum q_{n},\\v\in Conv(\sum Q_{n}),\\q_{n}\in Conv(Q_{n}).\\\end{cases}}$

В таком представлении набор суммируемых точек $q_{n}$ зависит от выбранной точки-суммы $v$.

Лемма Шепли — Фолкмана

Ллойд Шепли, лауреат Нобелевской премии по экономике (2012), является соавтором доказательства леммы наряду с Джоном Фолкманом.

Примем указанное представление точки $v=\sum q_{n}$.

Если размерность векторного пространства строго меньше числа слагаемых множеств

$D<N$,

то тогда, согласно лемме Шепли — Фолкмана, «овыпукление» требуется только для $D$ слагаемых множеств (их конкретный набор зависит от выбора точки $v$). Это позволяет выразить точку $v$ следующим образом:

$v=\sum _{1\leq {d}\leq {D}}{q_{d}}+\sum _{D+1\leq {n}\leq {N}}{q_{n}}$

при

$v\in {\sum _{1\leq {d}\leq {D}}{\operatorname {Conv} {(Q_{d})}}+\sum _{D+1\leq {n}\leq {N}}{Q_{n}}}.$

Иными словами, сумма точек $q_{d}$ принадлежит выпуклой оболочке суммы $D$ множеств (или меньшего их числа), а сумма точек $q_{n}$ принадлежит сумме оставшихся множеств-слагаемых.

Содержание леммы проиллюстрируем простейшим примером: каждую точку выпуклого множества [0, 2] можно представить как сумму целого числа из невыпуклого множества {0, 1} и вещественного числа из выпуклого множества [0, 1].

Размерность

Лемма позволяет делать и обратные выводы, касающиеся не множеств, но размерности векторного пространства. Если в некотором конечномерном вещественном векторном пространстве лемма выполняется для натурального числа $D$ и ни для какого числа меньше $D$, то размерность векторного пространства равна $D$. Разумеется, данное утверждение актуально только для конечномерных векторных пространств.

Теорема Шепли — Фолкмана и следствие Старра

Радиус описанной окружности (синий вектор) и внутренний радиус (зелёный вектор) множества тёмно-красных точек (их выпуклая оболочка обозначена красным пунктиром). Внутренний радиус меньше радиуса описанной окружности в большинстве случаев.

Шепли и Фолкман использовали лемму для доказательства своей теоремы, в которой устанавливалась верхняя граница расстояния между суммой Минковского и её выпуклой оболочкой, «овыпукленной» суммой. Теорема Шепли — Фолкмана гласит, что квадрат евклидова расстояния между любой точкой «овыпукленной» суммы $Conv(\sum Q_{n})$ и соответствующей ей точкой исходной суммы $\sum Q_{n}$ не превосходит значение суммы квадратов $D$ наибольших радиусов окружностей, описанных около множеств $Q_{n}$ (описанной сферой называется наименьшая сфера, включающая множество). Значение такой границы не зависит от числа $N$ слагаемых множеств, если $N>D$. Следовательно, расстояние равно нулю тогда и только тогда, когда сумма сама является выпуклым множеством. При $N>D$ верхняя граница зависит от размерности $D$, формы множеств-слагаемых и не зависит от количества слагаемых множеств.

Радиус описанной окружности превосходит внутренний радиус множества или, реже, равен ему. Внутренним радиусом называется наименьшее число $r$, такое, что для любой точки $q\in Conv(Q_{n})$ существует окружность радиуса $r$, содержащая те точки $Q_{n}$, которые охватывают центр окружности (то есть $q$). Внутренний радиус является характеристикой размеров невыпуклостей множества. Формально внутренний радиус множества можно определить так:

$r(Q_{n})=\sup \,\{q\in Conv(Q_{n})\}\inf \,\{T\subset Q_{n}\}rad(T).$

Следствие Старра к теореме установил новую (меньшую, чем у Шепли и Фолкмана) верхнюю границу между суммой и «овыпукленной» суммой:

согласно королларию Старра, квадрат евклидова расстояния между любой точкой $v\in Conv(\sum Q_{n})$ и соответствующей ей точкой множества $\sum Q_{n}$ ограничен суммой квадратов $D$ наибольших внутренних радиусов множеств $Q_{n}$.

Для простоты изложения теории меру расстояния, предложенную Старром, называют невыпуклостью (англ. non-convexity) множества. Граница, налагаемая королларием Старра на невыпуклость множества-суммы, зависит только от $D$ наибольших внутренних радиусов множеств-слагаемых и не зависит от числа слагаемых $N$ при $N>D$.

Подмножество $D$ слагаемых ($N>D$), точнее, их форма, определяет верхнюю границу расстояния между средним значением $N$ множеств по Минковскому

${\frac {1}{N}}(Q_{1}+Q_{2}+\ldots +Q_{n})$

и выпуклой оболочкой этой средней. При N, стремящемся к бесконечности, максимальное расстояние стремится к нулю (для множеств-слагаемых равномерно ограниченного размера).

Доказательство

Оригинальное доказательство леммы устанавливало лишь достоверность существования подобного представления точек, при этом алгоритм их нахождения в доказательстве представлен не был. Схожие доказательства были предложены Эрроу и Ханом, Касселсом, Шнейдером и другими учёными. Абстрактное и изящное доказательство представил Ивар Экеланд — его работа была впоследствии дополнена Артстейном. Некоторые доказательства не были опубликованы. В 1981 году Старр опубликовал итеративный метод вычисления представления заданной точки-суммы. Тем не менее присутствовавшее в работе доказательство было менее сильным, чем оригинальное.

Доказательство Экеланда

Пусть $v=\sum _{n}^{}q_{n}$, при этом все $q_{n}$ за вычетом $D$ принадлежат множеству $Q_{n}$.

Зададим отображение $\Phi$, действующее из $\mathbb {R} ^{Dn}$ в $\mathbb {R} ^{D}$, следующим образом:

$\Phi (q_{n})=\sum _{n}^{}q_{n}$.

По определению, $\sum _{n}^{}Q_{n}=\Phi (\prod _{n}^{}Q_{n})$.

Из линейности $\Phi$ следует, что

$Conv(\Phi (\prod _{n}^{}Q_{n}))=\Phi (Conv(\prod _{n}^{}Q_{n}))=\Phi (\prod _{n}^{}Conv(Q_{n}))$,

$Conv(\sum _{n}^{}Q_{n})=\sum _{n}^{}Conv(Q_{n}).$

Заметим, что $v\in Conv(\sum _{n}^{}Q_{n})$ тогда и только тогда, когда $v$ также принадлежит выпуклой оболочке конечного числа $m$ точек множества $\sum _{n}^{}Q_{n}$. Согласно теореме Каратеодори о выпуклой оболочке, $m\leqslant D+1$, однако в данном доказательстве этот результат использоваться не будет. Итак, мы можем представить $v$ следующим образом:

$v=\sum _{p=1}^{m}\alpha _{p}y_{p},$ где

$y_{p}\in \sum _{n}^{}Q_{n},$

$\alpha _{p}>0,\sum _{p=1}^{m}\alpha _{p}=1.$

В свою очередь, любой $y_{p}$ может быть представлен как

$y_{p}=\sum _{n}^{}y_{np},y_{np}\in Q_{n}.$

Обозначим m-множество $\{y_{np}\}_{1\leqslant p\leqslant m}$ как $F_{n}$. Очевидно, что для каждого $p$

$y_{p}\in \sum _{n}^{}F_{n},$

при этом

$v\in Conv(\sum _{n}^{}F_{n}).$

Таким образом, мы заменили каждое множество $Q_{n}$ конечным подмножеством $F_{n}$. Для дальнейших целей отметим, что $Conv(F_{n})$ являются многогранниками в $\mathbb {R} ^{D}$, а произведение $Conv(\prod _{n}^{}F_{n})$ является многогранником в $\mathbb {R} ^{Dn}$.

Обозначим прообраз элемента $v$ при отображении $\Phi$ буквой $H$. Нас интересует подмножество $A\in \mathbb {R} ^{Dn}$:

$A=H\cap Conv(\prod _{n}^{}F_{n})=\{q_{n}|q_{n}\in Conv(F_{n}),\sum _{n}^{}q_{n}=v\}.$

Предположение $v\in \sum _{n}^{}Conv(F_{n})$ означает, что $A$ непусто. Более того, так как $Conv(\prod _{n}^{}F_{n})$ есть многогранник, а $H$ — аффинное подпространство, то $A$ также является многогранником. Пусть $q_{n}$ — одна из его вершин. По-прежнему, $v=\sum _{n}^{}q_{n}$, где $q_{n}\in Conv(F_{n})$ при $q_{n}\in A$. Мы также докажем, что все точки $q_{n}$ за исключением по большей мере $D$ точек являются вершинами $Conv(F_{n})$. Так как любая вершина $Conv(F_{n})$ должна принадлежать $F_{n}$, доказательство этого утверждения будет служить доказательством леммы в целом.

Предположим, что указанное утверждение неверно, и существует $D+1$ точек $q_{n}$, которые не являются вершинами $F_{n}$. Обозначим их

$q_{n},\dots ,q_{D+1}.$

Для каждого $q_{n}$ существует вектор $z_{n}\in \mathbb {R} ^{D}$ и число $\varepsilon _{n}$ такие, что

$\forall t\in [-\varepsilon _{n},\varepsilon _{n}],q_{n}+tz_{n}\in Conv(F_{n}).$

Обозначим

$\varepsilon =\min _{1\leqslant n\leqslant D+1}\varepsilon _{n}.$

Итак, при существовании $D+1$ векторов в пространстве размерности $D$ между ними имеет место линейная зависимость. Следовательно, существуют не все равные нулю числа $\alpha _{1},\dots ,\alpha _{D+1}$ такие, что

$\sum _{n}^{D+1}\alpha _{n}z_{n}=0.$

Мы можем предположить, что $|\alpha _{n}|\leqslant 1$ при $1\leqslant n\leqslant D+1$. Теперь определим две принадлежащие $\mathbb {R} ^{Dn}$ точки $q_{n}'$ и $q_{n}''$:

$q_{n}'=q_{n}+\varepsilon \alpha _{n}z_{n},1\leqslant n\leqslant D+1,$

$q_{n}''=q_{n}-\varepsilon \alpha _{n}z_{n},1\leqslant n\leqslant D+1,$

$q_{n}'=q_{n}=q_{n}''$ в остальных случаях.

Из $\forall t\in [-\varepsilon _{n},\varepsilon _{n}],q_{n}+tz_{n}\in Conv(F_{n}).$ следует, что $q_{n}'$ и $q_{n}''$ принадлежат $Conv(F_{n})$. Кроме того,

$\sum _{n}^{}q_{n}'=\sum _{n}^{}q_{n}'+\varepsilon \sum _{n=1}^{D+1}\alpha _{n}z_{n}=v,$

$\sum _{n}^{}q_{n}''=\sum _{n}^{}q_{n}'-\varepsilon \sum _{n=1}^{D+1}\alpha _{n}z_{n}=v.$

Следовательно, точки $q_{n}'$ и $q_{n}''$ принадлежат $A$. При этом, очевидно,

$q_{n}=1/2q_{n}'+1/2q_{n}''.$

Вопреки предположению, $q_{n}$ не может быть вершиной $A$.

Приложения

Лемма позволяет исследователям экстраполировать результаты, актуальные для сумм Минковского выпуклых множеств, на прочие суммы необязательно выпуклых множеств. Инструменты Шепли, Фолкмана и Старра нашли применение в экономике, математической оптимизации и теории вероятностей.

Экономика

Потребитель предпочитает любую корзину товаров на кривой безразличия I₂ любой корзине на кривой I₁. Корзина (Q_x, Q_y), находящаяся в точке касания синей бюджетной линии к I₂, оптимальна и доступна, в то время как любая другая корзина на I₂ желанна, но недоступна.

Многие экономические отношения, зависимости и процессы можно смоделировать, представив их геометрическую интерпретацию. Следовательно, если некоторое множество, имеющее экономический смысл, поддаётся операции сложения Минковского, то лемма, теорема и их следствия становятся актуальными для модели данного экономического явления. Примером подобного множества является кривая безразличия — простая, но важная микроэкономическая модель потребления и полезности.

В микроэкономической теории принято допущение о том, что предпочтения потребителей определены на всём пространстве некоторых «корзин», то есть количественно определённых наборов различных товаров: потребители обладают точным знанием о своих предпочтениях и об их количественных характеристиках. Каждая корзина представлена неотрицательным вектором, координаты которого обозначают количество каждого рассматриваемого товара. На этом множестве корзин для каждого потребителя определяются кривые безразличия. Каждая кривая представляет собой геометрическое место точек, соответствующих тем корзинам, которые потребитель расценивает как эквивалентные по полезности. Другими словами, покупатель испытывает безразличие к тому, какая именно корзина (среди расположенных на одной кривой) ему достанется. В данной модели предполагается, что через некоторую корзину (точку) может проходить только одна кривая безразличия. Финансовые возможности покупателя при этом ограничены бюджетной линией (в двумерном пространстве). Таким образом, оптимальным для потребителя решением является выбор той корзины, которая расположена в точке касания бюджетной линии к некоторой кривой безразличия. Множеством предпочтений (англ. preference set) потребителя называется объединение некоторой кривой безразличия и всех точек, расположенных выше её графика (то есть совокупность некоторых одинаково ценных для потребителя корзин и всех других более ценных корзин). Отношение предпочтения потребителя является выпуклым, если это множество предпочтений выпукло.

Итак, если найдено оптимальное для потребителя решение, то бюджетная линия является опорной прямой лучшей доступной кривой безразличия. Положение бюджетной линии определено вектором цены и вектором дохода покупателя (точнее, вектором дохода и склонностью к потреблению). Следовательно, множество оптимальных корзин является функцией от цен, и эта функция называется спросом потребителя. Если множество предпочтений выпукло, то спрос потребителя также является выпуклым множеством при любой цене. Примером выпуклых функций спроса являются единственная оптимальная корзина и отрезок оптимальных корзин.

Невыпуклое отношение предпочтения

Если отношение предпочтения потребителя имеет вогнутости, потребитель может переходить между обособленными оптимальными корзинами, расположенными на кривой оптимальности. Кривая оптимальности (Optimal Pareto front) выделена чёрным цветом.

Впрочем, если множество предпочтений невыпукло, то при некоторых ценах формируется такая бюджетная линия, которая допускает выбор одной из двух обособленных оптимальных корзин. Например, владелец зоопарка, желающий приобрести льва или орла (оцениваемых одинаково), не может приобрести часть одного животного и часть другого — его множество предпочтений не является выпуклым. Так, потребитель отказывается от приобретения строго выпуклой комбинации товаров в пользу покупки лишь одного товара в произвольном количестве.

Если множество предпочтений потребителя невыпукло, тогда при некоторых ценах функция спроса потребителя не является связным пространством. Гарольд Хотеллинг говорил о несвязном спросе:

Если при рассмотрении покупательских кривых безразличия мы примем предположение об их волнообразном характере, выпуклом в некоторых местах и вогнутом в других, мы неизменно придём к выводу о том, что только выпуклые участки можно воспринимать как сколько-нибудь значимые, поскольку другие по существу ненаблюдаемы. Их можно обнаружить только по разрывам, которые могут возникнуть в спросе с изменением ценовых соотношений; [разрывы] приводят к резким скачкам точки касания «через пропасть», возникающим при вращении [касательной] прямой. Но, хотя эти разрывы и могут указывать на существование «пропастей», характеризовать их глубину они не смогут в принципе. Вогнутые участки кривых безразличия и их многомерные обобщения, если таковые существуют, навсегда останутся в неизмеримой неясности.

Оригинальный текст (англ.)

If indifference curves for purchases be thought of as possessing a wavy character, convex to the origin in some regions and concave in others, we are forced to the conclusion that it is only the portions convex to the origin that can be regarded as possessing any importance, since the others are essentially unobservable. They can be detected only by the discontinuities that may occur in demand with variation in price-ratios, leading to an abrupt jumping of a point of tangency across a chasm when the straight line is rotated. But, while such discontinuities may reveal the existence of chasms, they can never measure their depth. The concave portions of the indifference curves and their many-dimensional generalizations, if they exist, must forever remain in unmeasurable obscurity.

Сложность исследования невыпуклых предпочтений отмечали Херман Волд и Пол Самуэльсон. Последний, согласно Диверту, писал, что невыпуклости «окутаны вечной тьмой».

Тем не менее ряд публикаций 1959—1961 годов в журнале The Journal of Political Economy пролил свет на проблемы невыпуклых предпочтений. Ведущими исследователями в этой области стали Фаррелл, Бэйтор, Купманс и Ротенберг. В частности, в работе Ротенберга рассматривался вопрос приблизительной выпуклости сумм невыпуклых множеств. Статьи в JPE подтолкнули Шепли и Мартина Шубика к написанию работы, в которой описывались «овыпукленные» отношения предпочтения потребителей. Там же была впервые упомянута концепция «приблизительного равновесия» (англ. approximate equilibrium). Статья Шепли и Шубика, а также предшествующие публикации вдохновили Роберта Аумана на создание термина «квазиравновесие».

Доклад Старра 1969 года и современная экономика

Кеннет Эрроу, лауреат Нобелевской премии по экономике 1972 года, помогал Россу Старру в изучении невыпуклых экономик.

В годы учёбы в Стэнфордском университете Росс Старр проходил особый экономико-математический курс повышенной сложности под руководством Кеннета Эрроу. Эрроу, составивший в прошлом аннотированную библиографию публикаций на тему невыпуклости в экономике, передал её молодому коллеге. Свою семестровую работу Старр посвятил изучению общих равновесий некой вымышленной экономики, в которой невыпуклые отношения предпочтения заменялись их выпуклыми оболочками. Совокупный спрос в этой «овыпукленной» экономике представлял собой сумму выпуклых оболочек функций спроса потребителей при каждой цене. Идеи Старра заинтересовали Шепли и Фолкмана: в рамках частной переписки учёные доказали получившие их имя лемму и теорему, а затем эти результаты были опубликованы в работе Старра 1969 года.

Старру удалось обнаружить, что если число агентов на рынке превосходит товарную «размерность» (количество обмениваемых товаров), то общие равновесия «овыпукленной» экономики весьма близки к квазиравновесиям исходной экономики. Экономист получил строгое доказательство того, что в подобной ситуации имеет место по крайней мере одно квазиравновесие цен p_opt, обладающее следующими свойствами:

• при каждой цене все потребители могут выбирать оптимальные корзины (предпочитаемые и доступные с точки зрения бюджета),
• при ценах p_opt рынок каждого товара в «овыпукленной» экономике находится в равновесии (наблюдается равенство предложения и спроса),
• для каждого квазиравновесия цены способствуют почти полному очищению рынка: значение верхней границы расстояния между множеством равновесий «овыпукленной» экономики и множеством квазиравновесий исходной определяется королларием Старра.

Старр установил, что

в целом расхождение между размещением в вымышленной экономике [порождённой нахождением выпуклых оболочек всех потребительских и производственных множеств] и некоторым размещением в настоящей экономике ограничено независимо от числа экономических агентов.

Оригинальный текст (англ.)

in the aggregate, the discrepancy between an allocation in the fictitious economy generated by [taking the convex hulls of all of the consumption and production sets] and some allocation in the real economy is bounded in a way that is independent of the number of economic agents.

Результаты Шепли, Фолкмана и Старра получили применение и в других отраслях экономической науки: микроэкономике, теории общего равновесия, экономике общественного сектора (в том числе в теории провалов рынка), а также в теории игр, математической экономике и прикладной математике. Достижения Шепли, Фолкмана и Старра дали толчок внедрению теории меры множества и теории интегрирования в экономическую методологию.

Математическая оптимизация

Функция считается выпуклой, если её надграфик является выпуклым множеством.

Нелинейная оптимизация базируется на следующих основных понятиях:

• графиком функции $f$ называется множество пар аргумента функции $x$ и значения функции $f(x)$:

$Graph(f)=\{x,f(x)\},$

• надграфиком вещественной функции $f$ называется множество точек, расположенных выше графика функции:

$Epi(f)=\{x,u;f(x)<u\},$

• вещественная функция является выпуклой, если её надграфик является выпуклым множеством.

Например, функции $f(x)=x^{2}$ и $g(x)=|x|$ выпуклы, а функция $h(x)=sinx$ (синусоида) подобным свойством не обладает (синусоида невыпукла на интервале $[0,\pi ]$).

Задачи аддитивной оптимизации

Во многих задачах оптимизации целевая функция $f(x)$ сепарабельна, то есть является суммой многих слагаемых функций, каждая из которых имеет свой аргумент:

$f(x)=f(x_{1},\ldots ,x_{n})=\sum f_{n}(x_{n})$

В частности, целевые функции в задачах линейного программирования сепарабельны.

Оптимизационные задачи могут быть «овыпуклены» путём нахождения выпуклых оболочек слагаемых функций. Оптимальное решение такой задачи является пределом последовательности точек с координатами $(x_{j},f(x_{j}))$, принадлежащих множеству $\sum Conv(Graph(f_{n}))$. Оптимальная точка, согласно лемме, является суммой $D$ точек графиков «овыпукленных» слагаемых функций и некоторого числа точек графиков оригинальных функций.

Данный анализ был впервые опубликован Иваром Экеландом в 1974 году. Математик тогда пытался объяснить, почему сепарабельные задачи с большим числом слагаемых выпуклы при невыпуклости исходных слагаемых. За несколько месяцев до того французский учёный Клод Лемарешаль успешно применил итеративные методы выпуклой минимизации к решению невыпуклых задач. Решение двойственной задачи нелинейной минимизации не всегда несёт информацию, полезную для решения прямой задачи (однако для выпуклых прямых задач, удовлетворяющих условиям регулярности, это не так). Задача Лемарешаля была аддитивно сепарабельной, и каждая слагаемая функция была невыпуклой. Тем не менее решение двойственной задачи давало довольно точное приближение оптимального значения для прямой задачи. Анализ Экеланда прояснил причины успеха методов выпуклой минимизации, применяемых к большим и сепарабельным задачам с невыпуклыми слагаемыми функциями. Экеланд и другие учёные утверждали, что аддитивная сепарабельность позволяла считать задачу приблизительно выпуклой при невыпуклости слагаемых. Поворотным событием в данной области исследований стало обращение математиков к лемме Шепли — Фолкмана. Появление леммы стимулировало использование методов выпуклой минимизации для решения других классов задач с сепарабельными функциями.

Теория вероятностей и теория меры

Выпуклые множества часто изучаются в рамках теории вероятностей. Каждая точка, принадлежащая выпуклой оболочке непустого множества $Q$ в конечномерном пространстве, является математическим ожиданием простого случайного вектора, который принимает значения на множестве $Q$ (это следует из леммы Каратеодори. Таким образом, для непустого множества $Q$ набор математических ожиданий величин простого случайного вектора эквивалентен выпуклой оболочке множества $Q$ — следовательно, лемма может быть применена и в этой области. С другой стороны, инструментами для изучения выпуклых множеств в целом и леммы в частности обладает сама теория вероятностей. Результаты Шепли, Фолкамана и Старра широко применялись в вероятностной теории случайных множеств, например, для доказательства закона больших чисел, центральной предельной теоремы и теории больших отклонений. Чтобы избежать допущения о выпуклом характере всех случайных множеств, при доказательстве этих предельных теорем теории вероятностей применялись результаты Шепли, Фолкмана и Старра.

Лемма имеет приложения и в тех разделах теории меры, которые не связаны с вероятностью, например, в теориях объёма и векторной меры. Лемма позволяет уточнить теорему Брунна — Минковского, которая устанавливает отношение объёма множества-суммы и сумму объёмов множеств-слагаемых. Объём множества характеризуется мерой Лебега, которая определена для множеств евклидова пространства. Лемма также использовалась при доказательстве теоремы Ляпунова, которая указывает на то, что образ безатомной векторной меры является выпуклым. Векторная мера, значениями которой являются векторы, является обобщением понятия меры. К примеру, если $p_{1}$ и $p_{2}$ являются вероятностными мерами, определёнными на одном измеримом пространстве, тогда их функция-произведение $p_{1}p_{2}$ является векторной мерой, где $p_{1}p_{2}$ определена для каждого случайного события $\omega$:

$(p_{1}p_{2})(\omega )=(p_{1}(\omega ),p_{2}(\omega ))$

Теорема Ляпунова используется в математической экономике, теории релейных автоматических регуляторов и статистической теории. Данная теорема считается непрерывным аналогом леммы Шепли — Фолкмана, которую, в свою очередь, называют дискретным «двойником» теоремы Ляпунова.

Примечания

Комментарии

Использованная литература и источники

Литература

A—D

• Aardal K. Optima interview Claude Lemaréchal // Optima: Mathematical Programming Society newsletter. — 1995. — № 45. — С. 2–4.
• Anderson R. M. The Shapley–Folkman theorem // Economics 201B: Nonconvex preferences and approximate equilibria. — Economics Department, University of California, Berkeley, 2005.
• Arrow K., Hahn F. General competitive analysis. — North-Holland, 1980. — ISBN 0-444-85497-5.
• Artstein Z., Vitale R. A. A strong law of large numbers for random compact sets // The Annals of Probability. — 1975. — Т. 3, № 5. — С. 879–882. — doi:10.1214/aop/1176996275.
• Artstein Z. Discrete and continuous bang-bang and facial spaces, or: Look for the extreme points // SIAM Review. — 1980. — Т. 2, № 22. — С. 172–185. — doi:10.1137/1022026.
• Aubin J.-P., Ekeland I. Estimates of the duality gap in nonconvex optimization // Mathematics of Operations Research. — 1976. — № 3. — С. 225–245. — doi:10.1287/moor.1.3.225.
• Aubin J.-P. 14.2 Duality in the case of non-convex integral criterion and constraints // Mathematical methods of game and economic theory. — Dover Publications, Inc, 2007. — ISBN 978-0-486-46265-3.
• Aumann Y. R. J. Existence of competitive equilibrium in markets with a continuum of traders // Econometrica. — 1966. — Т. 34, № 1. — С. 1–17.
• Bator F. M. On convexity, efficiency, and markets // The Journal of Political Economy. — 1961. — Т. 69, № 5. — С. 480–483.
• Bator F. M. On convexity, efficiency, and markets: Rejoinder // The Journal of Political Economy. — 1961. — Т. 69, № 5. — С. 489.
• Bertsekas D. P. 5.6 Large scale separable integer programming problems and the exponential method of multipliers // Constrained optimization and Lagrange multiplier methods. — Athena Scientific, 1996. — ISBN 1-886529-04-3.
• Bertsekas D. P. 5.1.6 Separable problems and their geometry // Nonlinear Programming. — Athena Scientific, 1999. — ISBN 1-886529-00-0.
• Borwein M. J., O’Brien R. C. Cancellation characterizes convexity // Nanta Mathematica. — 1978. — № 11. — С. 100–102.
• Carter M. Foundations of mathematical economics. — MIT Press, 2001. — ISBN 0-262-53192-5.
• Cassels J. W. S. Measures of the non-convexity of sets and the Shapley–Folkman–Starr theorem // Mathematical Proceedings of the Cambridge Philosophical Society. — 1975. — № 3. — С. 433–436. — doi:10.1017/S0305004100051884.
• Cassels J. W. S. Appendix A Convex sets // Economics for mathematicians. — Cambridge University Press, 1981. — ISBN 0-521-28614-X.
• Cerf R. Large deviations for sums of i.i.d. random compact sets // Proceedings of the American Mathematical Society. — 1999. — Т. 127, № 8. — С. 2431–2436. — doi:10.1090/S0002-9939-99-04788-7.
• Di Guglielmo F. Nonconvex duality in multiobjective optimization // Mathematics of Operations Research. — 1977. — № 3. — С. 285–291. — doi:10.1287/moor.2.3.285.
• Diewert W. E. Duality approaches to microeconomic theory // Handbook of mathematical economics, Volume II. — North-Holland, 1982. — ISBN 978-0-444-86127-6.

E—O

• Ekeland I. Appendix I: An a priori estimate in convex programming // Convex analysis and variational problems. — Society for Industrial and Applied Mathematics, 1999. — ISBN 0-89871-450-8.
• Ellickson B. Competitive equilibrium: Theory and applications. — Cambridge University Press, 1994. — ISBN 978-0-521-31988-1.
• Farrell M. J. The Convexity assumption in the theory of competitive markets // The Journal of Political Economy. — 1959. — Т. 67, № 4. — С. 371–391.
• Farrell M. J. On Convexity, efficiency, and markets: A Reply // The Journal of Political Economy. — 1961. — Т. 69, № 5. — С. 484–489.
• Farrell M. J. The Convexity assumption in the theory of competitive markets: Rejoinder // The Journal of Political Economy. — 1961. — Т. 69, № 5. — С. 493.
• Florenzano M., Le Van C. Finite dimensional convexity and optimization. — Springer-Verlag, 2001. — ISBN 3-540-41516-5.
• Green J., Heller W. P. Mathematical analysis and convexity with applications to economics // Handbook of mathematical economics, Volume I. — North-Holland, 1981. — ISBN 0-444-86126-2.
• Guesnerie R. First-best allocation of resources with nonconvexities in production // Contributions to Operations Research and Economics: The twentieth anniversary of CORE (Papers from the symposium held in Louvain-la-Neuve, January 1987). — MIT Press, 1989. — ISBN 0-262-03149-3.
• Hildenbrand W. Core and equilibria of a large economy. — Princeton University Press, 1974. — ISBN 978-0-691-04189-6.
• Hiriart-Urruty J.-B., Lemaréchal C. XII Abstract duality for practitioners // Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. — Springer-Verlag, 1993. — ISBN 3-540-56852-2.
• Hotelling H. Demand functions with limited budgets // Econometrica. — 1935. — Т. 3, № 1. — С. 66–78.
• Howe R. E. On the tendency toward convexity of the vector sum of sets. — Cowles Foundation for Research in Economics, 1979.
• Ichiishi T. Game theory for economic analysis. — Academic Press, Inc., 1983. — ISBN 0-12-370180-5.
• Koopmans T. C. Allocation of resources and the price system // Three essays on the state of economic science. — McGraw–Hill Book Company, 1957.
• Koopmans T. C. Convexity assumptions, allocative efficiency, and competitive equilibrium // The Journal of Political Economy. — 1961. — Т. 69, № 5. — С. 478–479.
• Laffont J.-J. 3 Nonconvexities // Fundamentals of public economics. — MIT Press, 1988. — ISBN 0-262-12127-1.
• Lemaréchal C. Utilisation de la dualité dans les problémes non convexes. — National Institute for Research in Computer Science and Control, 1973.
• Mas-Colell A. A note on the core equivalence theorem: How many blocking coalitions are there? // Journal of Mathematical Economics. — 1978. — Т. 5, № 3. — С. 207–215. — doi:10.1016/0304-4068(78)90010-1.
• Mas-Colell A. 1.L Averages of sets // The Theory of general economic equilibrium: A differentiable approach. — Cambridge University Press, 1985. — ISBN 0-521-26514-2.
• Mas-Colell A. Non-convexity // The New Palgrave Dictionary of Economics. — Palgrave Macmillan, 1987.
• Mas-Colell A., Whinston M. D., Green J. 17.1 Large economies and nonconvexities // Microeconomic theory. — Oxford University Press, 1995. — ISBN 978-0-19-507340-9.
• Molchanov I. 3 Minkowski addition // Theory of random sets. — Springer-Verlag London Ltd, 2005. — ISBN 978-1-84996-949-9.
• Moore J. C. Mathematical methods for economic theory: Volume I. — Springer-Verlag, 1999. — ISBN 3-540-66235-9.

P—Z

• Puri M. L., Ralescu D. A. Limit theorems for random compact sets in Banach space // Mathematical Proceedings of the Cambridge Philosophical Society. — 1985. — № 1. — С. 151–158. — doi:10.1017/S0305004100062691.
• Rockafellar R. T. Convex analysis. — Princeton University Press, 1997. — ISBN 0-691-01586-4.
• Rothenberg J. Non-convexity, aggregation, and Pareto optimality // The Journal of Political Economy. — 1960. — Т. 68, № 5. — С. 435–468.
• Rothenberg J. Comments on non-convexity // The Journal of Political Economy. — 1961. — Т. 69, № 5. — С. 490–492.
• Ruzsa I. Z. The Brunn–Minkowski inequality and nonconvex sets // Geometriae Dedicata. — 1997. — № 67. — С. 337–348. — doi:10.1023/A:1004958110076.
• Salanié B. 7 Nonconvexitie // Microeconomics of market failures. — MIT Press, 2000. — ISBN 0-262-19443-0.
• Samuelson, P. A. The problem of integrability in utility theory // Economica. — 1950. — Т. 17, № 68. — С. 355–385.
• Schneider R. Convex bodies: The Brunn–Minkowski theory. — Cambridge University Press, 1993. — ISBN 0-521-35220-7.
• Schneider R., Weil W. Stochastic and integral geometry. — Springer, 2008. — ISBN 978-3-540-78858-4.
• Shapley L. S., Shubik M. Quasi-cores in a monetary economy with nonconvex preferences // Econometrica. — 1966. — Т. 34, № 4. — С. 805–827.
• Starr R. M. Quasi-equilibria in markets with non-convex preferences (Appendix 2: The Shapley–Folkman theorem) // Econometrica. — 1969. — № 37. — С. 35–37.
• Starr R. M. Approximation of Points of the Convex Hull of a Sum of Sets by Points of the Sum: An Elementary Approach // Journal of Economic theory. — 1981. — № 1. — С. 314–317.
• Starr R. M. 8 Convex sets, separation theorems, and non-convex sets in R^N // General equilibrium theory: An introduction. — 1997. — ISBN 0-521-56473-5.
• Starr R. M., Stinchcombe M. B. Markets, information and uncertainty: Essays in economic theory in honor of Kenneth J. Arrow. — Cambridge University Press, 1999. — ISBN 978-0-521-08288-4.
• Starr R. M. Shapley–Folkman theorem // The New Palgrave Dictionary of Economics. — Palgrave Macmillan, 2008.
• Tardella F. A new proof of the Lyapunov convexity theorem // SIAM Journal on Control and Optimization. — 1990. — № 2. — С. 478–481. — doi:10.1137/0328026.
• Trockel W. Market demand: An analysis of large economies with nonconvex preferences. — Springer-Verlag, 1984. — ISBN 3-540-12881-6.
• Varian H. R. 21.2 Convexity and size // Microeconomic Analysis. — W. W. Norton & Company, 1992. — ISBN 978-0-393-95735-8.
• Vind K. Edgeworth-allocations in an exchange economy with many traders // International Economic Review. — 1964. — Т. 5, № 2. — С. 165–177.
• Weil W. An application of the central limit theorem for Banach-space–valued random variables to the theory of random sets // Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete. — 1982. — Т. 60, № 2. — С. 203–208. — doi:10.1007/BF00531823.
• Wold H. A synthesis of pure demand analysis II // Skandinavisk Aktuarietidskrift. — 1943. — № 26. — С. 220–263.
• Wold H., Juréen L. Demand analysis: A study in econometrics. — John Wiley and Sons, Inc, 1953.

А—Я

• Ильин В. А., Позняк Э. Г. Линейная алгебра. — М.: Физико-математическая литература, 2010. — ISBN 978-5-9221-0481-4.
• Математическая энциклопедия под ред. И. М. Виноградова. — М.: Советская энциклопедия, 1977—1985.